import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description: 用两个队列实现栈
 * User: liangyuanzhang
 * Date: 2025-3-30
 * Time: 12:25
 */

/*
1.模拟的入栈操作是: 放到了 不为空的队列当中
2.模拟的出栈操作是: 把不为空的队列中的size-1个元素放到另一个队列当中。
  最后剩下的这一个就是我们 模拟“出栈”的元素
3.当获取栈顶元素时续需要定义中间变量而且size-1变成size
 */
public class MyStackUseQueue {

    Queue<Integer> qu1;
    Queue<Integer> qu2;

    public MyStackUseQueue() {
        //可以用LinkedList做
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    // 模拟入栈操作
    public void push(int x) { // 刚开始两个队列都为空
        if(!qu1.isEmpty()){
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }
    }

    // 模拟出栈操作
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size = qu1.size();
            for(int i = 0;i<size-1;i++){
                qu2.offer(qu1.poll()); // 把qu1的弹出(出队)方到qu2.循环结束后qu1就只剩我们模拟出栈的元素
            }
            return qu1.poll();// poll()是队列中出队的操作
        }else{
            int size = qu2.size();
            for(int i = 0;i<size-1;i++){
                qu1.offer(qu2.poll()); // 把qu2的弹出(出队)方到qu1.循环结束后qu2就只剩我们模拟出栈的元素
            }
            return qu2.poll();// poll()是队列中出队的操作
        }
    }

    public int top() { // 获取栈顶元素
        if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size = qu1.size();
            int val = 0; // 定义一个中间变量
            for(int i = 0;i<size;i++){ // 弹一个放到val 然后再从 val给qu2
                val = qu1.poll();
                qu2.offer(val);
            }
            return val;
        }else{
            int size = qu2.size();
            int val = 0; // 定义一个中间变量
            for(int i = 0;i<size;i++){ // 弹一个放到val 然后再从 val给qu2
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}
